In data communication networks, devices such as routers or switches are often used to transfer data from a source to a destination. In some existing systems, a switch fabric is used to transfer data from a source to a destination. The switch fabric may include multiple switch planes that operate independently. For example, in non-striped architectures where whole cells are switched by the switch fabric, the switch planes within the switch fabric may operate without synchronizing with each other. Although independent switch planes have certain performance advantages, they often lead to problems when cells arrive out of sequence and need to be reordered. Systems with independent switch planes typically require some buffering at each destination so that cells arriving out of sequence can be arranged to preserve their original order. As a result, if one switch plane fails or experiences heavy load, the delay in the arrival of certain cells may cause the buffers to over flow. For example, a stream of cells (numbered sequentially from 1 to 20 in the order of transmission) may be sent to a destination port via several switch planes. If, for example, cells 11-20 arrive before cell 10 arrives, then cells 11-20 are stored in a buffer and sent out after cell 10 is received. However, if the buffer size is limited to less than ten cells, the buffer would overflow.
Although increasing the buffer size helps to ameliorate the buffer overflow problem, the number of cells to be reordered may still exceed the amount of buffer space available, thus the problem is not completely eliminated. Furthermore, since it is preferable to use on-chip memory to implement the reorder buffers, increasing the reorder buffer size would increase the cost of the switch fabric components significantly. It would be desirable if the reorder buffer depth could be bounded to a limited size. It would also be useful if the buffer used for reordering purposes could be kept small enough so that on-chip memory could be used in a cost effective way.